<!DOCTYPE html>
<html  lang="zh">
<head>
    <meta charset="utf-8" />

<meta name="generator" content="Hexo 4.2.0" />

<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />

<title>P1337 [JSOI2004]平衡点 - Shaun-Shane</title>


    <meta name="description" content="题目链接">
<meta property="og:type" content="article">
<meta property="og:title" content="P1337 [JSOI2004]平衡点">
<meta property="og:url" content="http://yoursite.com/2020/04/16/P1337pivot/index.html">
<meta property="og:site_name" content="Shaun-Shane">
<meta property="og:description" content="题目链接">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="http://yoursite.com/images/pexels1.png">
<meta property="article:published_time" content="2020-04-16T10:54:03.000Z">
<meta property="article:modified_time" content="2020-04-16T13:13:56.341Z">
<meta property="article:author" content="NoOne">
<meta property="article:tag" content="洛谷">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://yoursite.com/images/pexels1.png">







<link rel="icon" href="/images/favicon.svg">


<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bulma@0.7.2/css/bulma.css">
<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.4.1/css/all.css">
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Ubuntu:400,600|Source+Code+Pro">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@9.12.0/styles/atom-one-light.css">


    
    
<style>body>.footer,body>.navbar,body>.section{opacity:0}</style>

    
    
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/lightgallery@1.6.8/dist/css/lightgallery.min.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/justifiedGallery@3.7.0/dist/css/justifiedGallery.min.css">

    
    
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/outdatedbrowser@1.1.5/outdatedbrowser/outdatedbrowser.min.css">

    
    
    
    
<link rel="stylesheet" href="/css/back-to-top.css">

    
    
    
    
    
    
    
    <link rel="stylesheet" href="/css/progressbar.css">
<script src="https://cdn.jsdelivr.net/npm/pace-js@1.0.2/pace.min.js"></script>
    
    
    


<link rel="stylesheet" href="/css/style.css">
</head>
<body class="is-3-column">
    <nav class="navbar navbar-main">
    <div class="container">
        <div class="navbar-brand is-flex-center">
            <a class="navbar-item navbar-logo" href="/">
            
                <img src="/images/logo.svg" alt="P1337 [JSOI2004]平衡点" height="28">
            
            </a>
        </div>
        <div class="navbar-menu">
            
            <div class="navbar-start">
                
                <a class="navbar-item"
                href="/">主页</a>
                
                <a class="navbar-item"
                href="/archives">归档</a>
                
                <a class="navbar-item"
                href="/categories">分类</a>
                
                <a class="navbar-item"
                href="/tags">标签</a>
                
                <a class="navbar-item"
                href="/about">关于</a>
                
            </div>
            
            <div class="navbar-end">
                
                    
                    <a class="navbar-item" target="_blank" rel="noopener" title="My Github" href="https://github.com/Shaun-Shane">
                        
                        <i class="fab fa-github"></i>
                        
                    </a>
                    
                
                
                <a class="navbar-item is-hidden-tablet catalogue" title="目录" href="javascript:;">
                    <i class="fas fa-list-ul"></i>
                </a>
                
                
                <a class="navbar-item search" title="搜索" href="javascript:;">
                    <i class="fas fa-search"></i>
                </a>
                
            </div>
        </div>
    </div>
</nav>

    
    <section class="section">
        <div class="container">
            <div class="columns">
                <div class="column is-8-tablet is-8-desktop is-9-widescreen has-order-2 column-main">
<div class="card">
    
    <div class="card-image">
        <span  class="image is-7by1">
            <img class="thumbnail" src="/images/pexels1.png" alt="P1337 [JSOI2004]平衡点">
        </span>
    </div>
    
    <div class="card-content article ">
        
        <div class="level article-meta is-size-7 is-uppercase is-mobile is-overflow-x-auto">
            <div class="level-left">
				<time class="level-item has-text-grey" datetime="2020-04-16T10:54:03.000Z"><i class="far fa-calendar-alt">&nbsp;</i>2020-04-16</time>
				
				<time class="level-item has-text-grey is-hidden-mobile" datetime="2020-04-16T13:13:56.341Z"><i class="far fa-calendar-check">&nbsp;</i>2020-04-16</time>
				
                <i class="far fa-folder-open">&nbsp;</i>
                
                <div class="level-item">
                <a class="has-link-grey -link" href="/categories/%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB/">模拟退火</a>
                </div>
                
                <i class="far fa-clock">&nbsp;</i>
                
                <span class="level-item has-text-grey">
                    
                    
                    2 分钟 读完 (大约 230 个字)
                </span>
                
                
            </div>
        </div>
        
        <h1 class="title is-size-3 is-size-4-mobile has-text-weight-normal">
            
                P1337 [JSOI2004]平衡点
            
        </h1>
        <div class="content">
            <p><a href="https://www.luogu.com.cn/problem/P1337">题目链接</a><br><a id="more"></a><br>模拟退火模板题，有空再跟新…</p>
<h1 id="Code"><a href="#Code" class="headerlink" title="Code"></a>Code</h1><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">constexpr</span> <span class="keyword">int</span> MAXN = <span class="number">1e3</span> + <span class="number">3</span>;</span><br><span class="line"><span class="keyword">constexpr</span> <span class="keyword">double</span> down = <span class="number">0.996</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> n;</span><br><span class="line">pair&lt;pair&lt;<span class="keyword">int</span>, <span class="keyword">int</span>&gt;, <span class="keyword">int</span>&gt; obj[MAXN];</span><br><span class="line"><span class="keyword">double</span> x, y, Ep;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">double</span> <span class="title">energy</span><span class="params">(<span class="keyword">double</span> x, <span class="keyword">double</span> y)</span> </span>&#123; <span class="comment">//重力势能越小越稳定</span></span><br><span class="line">    <span class="keyword">double</span> E = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">        <span class="keyword">double</span> dx = x - obj[i].first.first;</span><br><span class="line">        <span class="keyword">double</span> dy = y - obj[i].first.second;</span><br><span class="line">        E += <span class="built_in">sqrt</span>(dx * dx + dy * dy) * obj[i].second;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> E;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">void</span> <span class="title">SA</span><span class="params">()</span> </span>&#123; <span class="comment">//SimulateAnneal</span></span><br><span class="line">    <span class="keyword">double</span> T = <span class="number">3000</span>;</span><br><span class="line">    <span class="keyword">while</span> (T &gt; <span class="number">1e-14</span>) &#123;</span><br><span class="line">        <span class="keyword">double</span> randx = x + (rand() * <span class="number">2</span> - RAND_MAX) * T;</span><br><span class="line">        <span class="keyword">double</span> randy = y + (rand() * <span class="number">2</span> - RAND_MAX) * T;</span><br><span class="line">        <span class="keyword">double</span> E = energy(randx, randy);</span><br><span class="line">        <span class="keyword">double</span> delta = E - Ep;</span><br><span class="line">        <span class="keyword">if</span> (delta &lt; <span class="number">0</span>) &#123; <span class="comment">//E更小 答案更优</span></span><br><span class="line">            x = randx, y = randy, Ep = E;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (<span class="built_in">exp</span>(-delta / T) * RAND_MAX &gt; rand()) &#123; <span class="comment">//根据多项式概率接受</span></span><br><span class="line">            x = randx, y = randy;</span><br><span class="line">        &#125;</span><br><span class="line">        T *= down;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="built_in">std</span>::ios::sync_with_stdio(<span class="literal">false</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>), <span class="built_in">cout</span>.tie(<span class="number">0</span>);</span><br><span class="line">    <span class="built_in">cin</span> &gt;&gt; n;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">        <span class="built_in">cin</span> &gt;&gt; obj[i].first.first &gt;&gt; obj[i].first.second &gt;&gt; obj[i].second;</span><br><span class="line">        x += obj[i].first.first, y += obj[i].first.second;</span><br><span class="line">    &#125;</span><br><span class="line">    x /= n, y /= n, Ep = energy(x, y);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; <span class="number">4</span>; i++) SA();</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; setprecision(<span class="number">3</span>) &lt;&lt; fixed &lt;&lt; x &lt;&lt; <span class="string">" "</span> &lt;&lt; y &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
        </div>
		
			<ul class="post-copyright">
			<li><strong>文章作者：</strong>Shaun-Shane</li>
			<li><strong>文章链接：</strong><a href="/2020/04/16/P1337pivot/" target="_blank" title="P1337 [JSOI2004]平衡点">http://yoursite.com/2020/04/16/P1337pivot/</a></li>
			<li><strong>发布时间：</strong>2020-04-16</li>
			<li><strong>更新时间：</strong>2020-04-16</li>
			<li><strong>版权声明：</strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" rel="external nofollow" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明出处！
			</li>
			</ul>
		
        
        <hr style="height:1px;margin:1rem 0"/>
        <div class="level is-size-7 is-uppercase">
            <div class="level-start">
                <div class="level-item">
                    <i class="fas fa-tags has-text-grey"></i>&nbsp;
                    <a class="has-link-grey -link" href="/tags/%E6%B4%9B%E8%B0%B7/" rel="tag">洛谷</a>
                </div>
            </div>
        </div>
        
        
        
    </div>
</div>





<div class="card card-transparent">
    <div class="level post-navigation is-flex-wrap is-mobile">
        
        <div class="level-start">
            <a class="level level-item has-link-grey  article-nav-prev" href="/2020/04/16/P4098ALO/">
                <i class="level-item fas fa-chevron-left"></i>
                <span class="level-item">P4098ALO</span>
            </a>
        </div>
        
        
        <div class="level-end">
            <a class="level level-item has-link-grey  article-nav-next" href="/2020/04/13/hello-world/">
                <span class="level-item">Hello World</span>
                <i class="level-item fas fa-chevron-right"></i>
            </a>
        </div>
        
    </div>
</div>



</div>
                




<div class="column is-4-tablet is-4-desktop is-3-widescreen  has-order-1 column-left ">
    
        
<div class="card widget">
    <div class="card-content">
        <nav class="level">
            <div class="level-item has-text-centered" style="flex-shrink: 1">
                <div>
                    
                    <figure class="image is-128x128 has-mb-6">
                        <img class="" src="/images/avatar.png" alt="">
                    </figure>
                    
                    
                    
                </div>
            </div>
        </nav>
        <nav class="level is-mobile">
            <div class="level-item has-text-centered is-marginless">
                <div>
                    <p class="heading">
                        文章
                    </p>
                    <a href="/archives">
                        <p class="title has-text-weight-normal">
                            4
                        </p>
                    </a>
                </div>
            </div>
            <div class="level-item has-text-centered is-marginless">
                <div>
                    <p class="heading">
                        分类
                    </p>
                    <a href="/categories">
                        <p class="title has-text-weight-normal">
                            7
                        </p>
                    </a>
                </div>
            </div>
            <div class="level-item has-text-centered is-marginless">
                <div>
                    <p class="heading">
                        标签
                    </p>
                    <a href="/tags">
                        <p class="title has-text-weight-normal">
                            2
                        </p>
                    </a>
                </div>
            </div>
        </nav>
        
        
        
    </div>
</div>
    
        

    <div class="card widget column-left is-sticky" id="toc">
        <div class="card-content">
            <div class="menu">
                <h3 class="menu-label">
                    目录
                </h3>
                <ul class="menu-list"><li>
        <a class="is-flex" href="#Code">
        <span class="has-mr-6">1</span>
        <span>Code</span>
        </a></li></ul>
            </div>
        </div>
    </div>

    
    
        <div class="column-right-shadow is-hidden-widescreen ">
        
        </div>
    
</div>


                

            </div>
        </div>
    </section>
    <footer class="footer">
    <div class="container">
        <div class="level">
            <div class="level-start has-text-centered-mobile">
                <a class="footer-logo is-block has-mb-6" href="/">
                
                    <img src="/images/logo.svg" alt="P1337 [JSOI2004]平衡点" height="28">
                
                </a>
                <p class="is-size-7">
                &copy; 2020 NoOne&nbsp;
                Powered by <a href="https://hexo.io/" target="_blank" rel="noopener">Hexo</a> & <a
                        href="https://github.com/ppoffice/hexo-theme-icarus" target="_blank" rel="noopener">Icarus</a>
                
                </p>
            </div>
            <div class="level-end">
            
                <div class="field has-addons is-flex-center-mobile has-mt-5-mobile is-flex-wrap is-flex-middle">
                
                <p class="control">
                    <a class="button is-white is-large" target="_blank" rel="noopener" title="Creative Commons" href="https://creativecommons.org/">
                        
                        <i class="fab fa-creative-commons"></i>
                        
                    </a>
                </p>
                
                <p class="control">
                    <a class="button is-white is-large" target="_blank" rel="noopener" title="Attribution 4.0 International" href="https://creativecommons.org/licenses/by/4.0/">
                        
                        <i class="fab fa-creative-commons-by"></i>
                        
                    </a>
                </p>
                
                <p class="control">
                    <a class="button is-white is-large" target="_blank" rel="noopener" title="Download on GitHub" href="https://github.com/ppoffice/hexo-theme-icarus">
                        
                        <i class="fab fa-github"></i>
                        
                    </a>
                </p>
                
                </div>
            
            </div>
        </div>
    </div>
</footer>
    <script src="https://cdn.jsdelivr.net/npm/jquery@3.3.1/dist/jquery.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/moment@2.22.2/min/moment-with-locales.min.js"></script>
<script>moment.locale("zh-CN");</script>


<script>
var IcarusThemeSettings = {
    site: {
        url: 'http://yoursite.com',
        external_link: {"enable":true,"exclude":[]}
    },
    article: {
        highlight: {
            clipboard: true,
            fold: 'folded'
        }
    }
};
</script>


<script src="https://cdn.jsdelivr.net/npm/clipboard@2.0.4/dist/clipboard.min.js" defer></script>





<script src="/js/animation.js"></script>



<script src="https://cdn.jsdelivr.net/npm/lightgallery@1.6.8/dist/js/lightgallery.min.js" defer></script>
<script src="https://cdn.jsdelivr.net/npm/justifiedGallery@3.7.0/dist/js/jquery.justifiedGallery.min.js" defer></script>
<script src="/js/gallery.js" defer></script>



<div id="outdated">
    <h6>Your browser is out-of-date!</h6>
    <p>Update your browser to view this website correctly. <a id="btnUpdateBrowser" href="http://outdatedbrowser.com/">Update
            my browser now </a></p>
    <p class="last"><a href="#" id="btnCloseUpdateBrowser" title="Close">&times;</a></p>
</div>
<script src="https://cdn.jsdelivr.net/npm/outdatedbrowser@1.1.5/outdatedbrowser/outdatedbrowser.min.js" defer></script>
<script>
    document.addEventListener("DOMContentLoaded", function () {
        outdatedBrowser({
            bgColor: '#f25648',
            color: '#ffffff',
            lowerThan: 'flex'
        });
    });
</script>


<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.5/unpacked/MathJax.js?config=TeX-MML-AM_CHTML" defer></script>
<script>
document.addEventListener('DOMContentLoaded', function () {
    MathJax.Hub.Config({
        'HTML-CSS': {
            matchFontHeight: false
        },
        SVG: {
            matchFontHeight: false
        },
        CommonHTML: {
            matchFontHeight: false
        },
        tex2jax: {
            inlineMath: [
                ['$','$'],
                ['\\(','\\)']
            ]
        }
    });
});
</script>


<a id="back-to-top" title="回到顶端" href="javascript:;">
    <i class="fas fa-chevron-up"></i>
</a>
<script src="/js/back-to-top.js" defer></script>














<script src="/js/main.js" defer></script>

    
    <div class="searchbox ins-search">
    <div class="searchbox-container ins-search-container">
        <div class="searchbox-input-wrapper">
            <input type="text" class="searchbox-input ins-search-input" placeholder="想要查找什么..." />
            <span class="searchbox-close ins-close ins-selectable"><i class="fa fa-times-circle"></i></span>
        </div>
        <div class="searchbox-result-wrapper ins-section-wrapper">
            <div class="ins-section-container"></div>
        </div>
    </div>
</div>
<script>
    (function (window) {
        var INSIGHT_CONFIG = {
            TRANSLATION: {
                POSTS: '文章',
                PAGES: '页面',
                CATEGORIES: '分类',
                TAGS: '标签',
                UNTITLED: '(无标题)',
            },
            CONTENT_URL: '/content.json',
        };
        window.INSIGHT_CONFIG = INSIGHT_CONFIG;
    })(window);
</script>
<script src="/js/insight.js" defer></script>
<link rel="stylesheet" href="/css/search.css">
<link rel="stylesheet" href="/css/insight.css">
    
</body>
</html>
